package cn.itcast.zt.leetcode.array;

import java.util.Arrays;

/**
 * 数组相关的算法合集
 */
public class Array_Algorithm {
    /**
     * 两数之和  1
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标
     */
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2] ;

        for(int i = 0 ; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j ;
                }
            }
        }

        return result ;
    }

    /**
     * 合并两个有序数组
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i != n; i++) {
            nums1[m + i] = nums2[i] ;
        }

        Arrays.sort(nums1);
    }

    /**
     * 移除数组中的元素
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        int n = nums.length ;
        int left = 0 ;

        for (int right = 0; right < n; right ++) {
            if (nums[right] != val) {
                nums[left] = nums[right] ;
                left ++ ;
            }
        }

        return left ;
    }

    /**
     * 买卖股票的最佳时机
     */
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE ;
        int maxProfit = 0 ;
        for(int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i] ;
            }else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice ;
            }
        }

        return maxProfit ;
    }

    /**
     * 169. 多数元素
     * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素
     */
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2] ;
    }

    /**
     * 53. 最大子数组和
     */
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x) ;
            maxAns = Math.max(maxAns, pre) ;
        }

        return maxAns ;
    }

    /**
     * 26. 删除有序数组中的重复项
     */
    public int removeDuplicates(int[] nums) {
        int n = nums.length ;
        if (n == 0) {
            return 0 ;
        }

        int fast = 1, slow = 1 ;
        while(fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast] ;
                ++slow ;
            }

            ++fast ;
        }

        return slow ;
    }

    /**
     * 167. 两数之和 II - 输入有序数组
     */
    public int[] twoSumData(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int low = i + 1 ;
            int hight = numbers.length - 1 ;

            while(low <= hight) {
                int mid = low + (hight - low) / 2 ;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1} ;
                }else if(numbers[mid] > target - numbers[i]) {
                    hight = mid - 1 ;
                }else {
                    low = mid + 1 ;
                }
            }
        }

        return new int[] {-1, -1} ;
    }

    /**
     * 长度最小的子数组
     */
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length ;
        if (n == 0) {
            return 0 ;
        }

        Integer ans = Integer.MAX_VALUE ;
        for (int i = 0; i < n; i++) {
            int sum = 0 ;
            for (int j = i; j < n; j++) {
                sum += nums[j] ;
                if (sum >= s) {
                    ans = Math.min(ans, j - i + 1) ;
                    break;
                }
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans ;
    }

    /**
     * 912. 排序数组
     */
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[]{} ;
        }

        int len = nums.length ;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - i - 1 ; j++) {
                if (nums[j] > nums[j+1]) {
                    int temp = nums[j] ;
                    nums[j] = nums[j+1] ;
                    nums[j+1] = temp ;
                }
            }
        }

        return nums ;
    }

    /**
     * 数组中只出现一次的数
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        int single = 0 ;
        for (int num : nums) {
            single ^= num ;
        }

        return single ;
    }

    /**
     * 215. 数组中的第K个最大元素
     */
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums) ;
        return nums[nums.length - k] ;
    }
}
